<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        // 创建一个 创建树形节点的类
        class createTree {
            constructor(data) {
                // data:数字
                this.data = data; // 数据域
                this.left = null; // 左指针域
                this.right = null; // 右指针域
                this.root = this; // 记录当前节点的信息
            }
        }

        // 操作树形节点的类
        class BSTree {
            constructor() {
                // 记录树形结构
                this.root = null
            }

            // 添加
            // 1.创建树形节点
            // 2.找一个合适的位置 添加节点
            insert(data) {
                // 1.创建
                const newNode = new createTree(data)

                // 创建一个添加树形结构的方法
                const insertNode = (node, newNode) => {
                    // 判断 数据域 与 新添加的节点的大小
                    if (node.data > newNode.data) {
                        if (node.left === null) {
                            node.left = newNode
                        } else insertNode(node.left, newNode)
                    } else {
                        if (node.right === null) {
                            node.right = newNode
                        } else insertNode(node.right, newNode)
                    }
                }

                // 2.添加
                if (this.root === null) {
                    // 如果为空树的话， 就直接赋值新节点
                    this.root = newNode
                } else {
                    insertNode(this.root, newNode)
                }
            }

            // 获取最大值
            getMax() {
                // 最大值 一定是右指针域

                // 创建一个查找最大值的方法
                const getMaxNode = (node) => {
                    return node ? (node.right ? getMaxNode(node.right) : node) : null
                }

                return getMaxNode(this.root)
            }

            // 获取最小值
            getMin(root) {
                // 最小值一定是在左指针域

                // 创建一个查找最小值的方法
                const getMinNode = (node) => {
                    return node ? (node.left ? getMinNode(node.left) : node) : null
                }

                return getMinNode(root || this.root)
            }

            // 精确查找某一个树形节点
            search(data) {
                // 判断是否为空树
                if (this.root === null) return null

                // 创建 精确查找的方法
                const searchNodeFun = (node, searchData) => {
                    // 判断当前数据域 是否 等于 我要查找的数
                    if (node.data === searchData) {
                        return node
                    } else if (node.data > searchData) {
                        // 如果当前数据域 不等于 我要插好的数 ，就要使用当前数据域比较我要查找的数，如果当前数据域大于我要查找的数，就精确查找的方法 去左指针域查找
                        return searchNodeFun(node.left, searchData)
                    } else {
                        return searchNodeFun(node.right, searchData)
                    }
                }

                return searchNodeFun(this.root, data)
            }

            // 删除
            delete(data) {
                if (this.root === null) return null

                // 创建删除的方法
                const deleteNode = (node, data) => {
                    if (node.data === data) {
                        // 删除的操作

                        // 判断 左右指针域是否都不存在
                        if (node.left === null && node.right === null) return null;

                        // 如果左指针域为空 右指针域不为空的话 就直接返回右指针域
                        if (node.left === null) return node.right

                        // 如果右指针域为空 左指针域不为空的话 就直接返回左指针域
                        if (node.right === null) return node.left;

                        // 如果左右指针域都存在 就找最大值，代替当前数据域
                        const _node = this.getMax(this.right)

                        node.data = _node.data

                        // 让右指针域 重新 整理 数据
                        node.right = deleteNode(node.right, _node.data);

                        return node

                    } else if (node.data > data) {
                        // 让右指针域 等于 删除完成之后的节点
                        node.left = deleteNode(node.left, data)
                        return node
                    } else {
                        // 让左指针域 等于 删除完成之后的节点
                        node.right = deleteNode(node.right, data)
                        return node
                    }
                }

                deleteNode(this.root, data)

            }

            // 先序遍历
            inOrder() {
                // 遍历时存放的数组
                const arr = []

                // 创建遍历的方式
                const orderNode = (node) => {
                    if (node !== null) {
                        arr.push(node.data)

                        orderNode(node.left)

                        orderNode(node.right)
                    }
                };

                orderNode(this.root)

                // 返回遍历之后的结果
                return arr
            }

            // 中序遍历
            middleOrder() {
                // 遍历时存放的数组
                const arr = []

                // 创建遍历的方式
                const orderNode = (node) => {
                    if (node !== null) {
                        orderNode(node.left)

                        arr.push(node.data)

                        orderNode(node.right)
                    }
                };

                orderNode(this.root)

                // 返回遍历之后的结果
                return arr
            }

            // 后续遍历
            nextOrder() {
                // 遍历时存放的数组
                const arr = []

                // 创建遍历的方式
                const orderNode = (node) => {
                    if (node !== null) {
                        orderNode(node.left)

                        orderNode(node.right)

                        arr.push(node.data)
                    }
                };

                orderNode(this.root)

                // 返回遍历之后的结果
                return arr
            }
        }

        const myTree = new BSTree();

        // 添加
        myTree.insert(6)

        // 批量添加
        const arr = [7, 10, 3, 5, 11, 9, 27, 14, 18]

        arr.forEach(item => {
            myTree.insert(item)
        })

        console.log(myTree.inOrder())
        console.log(myTree.middleOrder())
        console.log(myTree.nextOrder())
    </script>
</body>

</html>